\chapter{公钥密码体制(public key cryptography)}
1976年W. Diffie和N. E. Hellman发表了著名的文章“New Directions in Cryptography”，奠定了公钥密码的基础，与传统的密码系统不同的是不需要额外分发密钥的可信信道，加密密钥和解密密钥是本质上不同的，知道一个密钥不能有效地计算出来另外一个。图\ref{convetion-public-coompare}是传统加密体系和公钥加密体系框图的对比。
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{convention-public-compare.png}
	\caption{“New Directions in Cryptography”一文中传统加密和公钥加密框图比较}
	\label{convetion-public-coompare}
\end{figure}
公钥密码体系中，信息传递者有一个私钥(SK,secrete key)和一个公钥(PK,public key)，公钥PK是公开的，现在有个两个信息传递者A和B(或者是Alice:/) 和Bob:/)  )，其公私钥分别为$SK_a,PK_a,SK_b,PK_b$，这时A和B之间不需要进行密钥协商或者交换就可以进行保密通信，假如A要发信息给B，A只需要用B的公钥对信息进行加密$c=E_{PK_b}(m)$，然后把加密后的信息c发给B,B收到后，用其私钥进行解密$m=D_{SK_b}(c)$,恢复出m。\par
\section{陷门单向函数(trap-door one-way function)}
公钥密码体系的思想很好理解，但是要构造这样一个体系，并且能够抵抗住密码分析者的攻击却不是一件容易的事情，要求密码分析者从公开的各种信息中无法获得密钥信息和有效的解密办法，Diffie和Hellman在提出公钥密码思想后也给出了如何构造这种密码体系的基本方向或者方法，那就是寻找一个陷门单向函数。\par
陷门单向函数是这样一类函数族$y=f(x,k)$,其中k为参数，对于每个k，x和f(x,k)一一对应，给定x和k，f(x,k)很“容易”计算，但是若给定y(或者说f(x,k))和k，计算x是“困难”的，这就是说f(x,k)是个单向函数。\par
如何存在一个“陷门信息"$k'=d(k)$及函数g(y,k')，使得当$y=f(x,k)$时,$x=g(y,k')$，并且在给定y和k'时，$g(y,k')$是"容易"计算的，也就是说陷门信息使得给定y和k'时，可以“容易”地计算x。\par
仅仅具备单向性的函数可以用来存储口令文件(例如Hash函数)，而陷门单向函数则使用建立公钥密码系统.
\section{MH方法\cite{qing-cry}}
1978年，美国斯坦福大学的R. C. Merkle和M. E. Hellman在"Hiding information and signatures in trapdoor knapsacks"一文中，建立了一种基于陷门背包的公钥密码系统。
\subsection{0-1背包问题(0-1 Knapsack Problem)}
0-1背包问题是指这样一个问题。有n件物品和容量为m的背包，知道每件物品的重量以及价值，每件物品只有一件供你选择，你可以选择装还是不装，找到一种装法，使背包里的物品重量不超过背包容量且价值最大。\par
我们看看0-1背包问题的一个变种，有n件物品和容量为m的背包，知道每件物品的重量以及价值分别为$w_i,v_i$，我们先不考虑背包容量，我们只找到一种装法使得物品价值正好为S，我们用数学语言劳描述就是，有一个正整数S和一个背包向量$V=(v_1,v_2,\ldots,v_n)$，找到一个二进制向量$X=(x_1,x_2,\ldots,x_n)$,使得$S=\sum_{i=1}^{n}x_iv_i$。“这个问题是一个著名的NP问题，目前解一般背包问题最好的算法需要$O(2^{n/2})$,存储量$O(2^{n/4})$。但是背包问题的困难程度和背包向量的选择关系很大，如果$V=(1,2,4,\ldots,2^{n-1})$，给定S求X就会很容易”\cite{qing-cry}。\par
上面变种的0-1背包问题中还有一种特殊背包问题，我们称为简单背包(simple knapsack),简单背包问题中的背包向量V是一个超上升(super increasing)向量,即$v_i > \sum_{j=1}^{i-1}$，对于简单背包问题可以用线性时间解出，也就是其是个P类问题。
\subsection{MH方法}
\subsubsection{陷门单向函数构造}
简单背包问题是一个P类问题，MH方法的本质是将简单背包变成一个陷门背包，如果不知道陷门信息，就是一个难解问题，知道陷门，就是一个容易解的问题。\par
下面我肯看看MH实现方法。\par
首先选择一个简单背包向量$V=(v_1,v_2,\ldots,v_n)$，给定S，我们容易求得$X=(x_1,x_2,\ldots,x_n)$，使得$S=\sum_{i=1}^{n}x_iv_i$。然后我们选择一个整数t，t满足$t>\sum_{i=1}^{n}v_i$,选择一个与t互素的整数p，计算$p^{-1},pp^{-1}=1 mod\ t$，我们计算一个新向量$V'=pV (mod\ t)$,新向量中的元素伪随机分布,故单纯看$S=XV'$是个困难问题，但是如果我们知道$p^{-1},m$，我们再可以把$S=XV'$进行如下转换：\par
\begin{equation}
	S'=p^{-1}S(mod\ t)\\
	=p^{-1}XV'(mod\ t)\\
	=p^{-1}XpV(mod\ t)\\
	=p^{-1}pXV(mod\ t)\\
	=XV(mod\ t)\\
\end{equation}
因为$t>\sum_{i=1}^{n}v_i$，所以有$S'=XV$，我们知道这是个容易计算为问题，所以我们求得X，就是初始困难问题的解。
\subsubsection{加密方法}
对于MH方法，用户公布困难背包向量V',V'是公钥,$(V,t,p^{-1})$保密，$(t,p^{-1})$为私钥，由于V可以根据私钥和公钥计算出来，也可以不做存储或者考虑。加密时将信息预处理为长度为n的二进制块$X=(x_1,x_2,\ldots,x_n)$，加密过程为$C=E_{V'}(X)=\sum_{i=1}^{n}(x_iv'_i)$,解密过程为首先计算$C'=p^{-1}C$，然后求解X$C'=XV$。


\section{RSA}
1978年，美国的麻省理工学院的R. L. Rivest,A. Shamir和M. Adleman在其论文"A method for obtaining digital signatures and public-key cryptosystems"中提出了一种实现Diffie——Hellman公钥思想的方法，简称为RSA方法。\par
1982年，Rivest、Shamir和Adleman三个创始人正式成立了RSA Data Security公司，1989年刚刚发展起来的互联网采用了RSA加密软件，1994年RSA源代码在互联网上被匿名公布，RSA公司成立后不断发展，是一家顶级的安全服务公司。\footnote{信息来源于\url{https://blog.csdn.net/wangjianno2/article/details/19262887}}\par
\subsection{RSA依赖的困难问题}
RSA依赖的困难问题时：素分解是个计算上困难的问题。\par
但是如何有一组素数，计算出这组素数的合数，却是一个容易的问题。
\subsection{RSA加密方法}
\begin{enumerate}
	\item 用户选取两个不同的大素数p和q，计算$n=pq$,我们知道$\phi(n)=(p-1)(q-1)$.
	\item 选一个正整数d，满足$gcd(d,\phi(n))=1$.
	\item 计算d模$\phi(n)$的逆元e，也就是说$ed=1(mod\ \phi(n))$.
	\item (e,n)做为公钥，(d,n)做为私钥.
	\item 加密：RSA是分组加密，取一个明文分组M，$0 \leq M \leq n-1$\footnote{对与实际加密的数据可以按照一定方法把数据变换为符合合格要求，比如将其变为n进制编码},$C=E_e(M)=M^e(mod\ n)$。
	\item 解密：$M'=D_d(C)=C^d(mod\ n)=(M^e)^d(mod\ n)=M^{ed}(mod\ n)=M(mod\ n)$
\end{enumerate}
\par
\vspace{1cm}
已知公钥(e,n)，如果能够计算出n的素分解，也就是知道p和q，那么就能很容易计算出d，可见RSA算法依赖的困难问题就是分解因子问题。

\subsection{RSA简单示例}

说一个RSA系统是多少位的，通常是指模n转换位二进制后是多少位。下面我们给出一个12位RSA的加密解密方法\footnote{此节采用的例子素材来源于https://www.jianshu.com/p/4e302869d057}。\par

(1) 生成公私钥对\par
RSA是非对称加密，有公钥和私钥，公钥公开给加密方加密，私钥留给自己解密，是不公开的。\par
1.随机选两个素数，用p、q来代替 （素数的数值越大，位数就越多，可靠性就越高。假设我们取p = 47，q = 59。\par
2.计算这两个素数的乘积，$n =p \times q = 47 \times 59 = 2773$,n的长度就是公钥长度。2773写成二进制是101011010101，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。\par
3.计算n的欧拉函数$\phi(n)$,$\phi(n) = (p-1)(q-1) $,$\phi(2773) = (47 - 1) \times (59 - 1) = 46 \times 58 = 2668$.\par
4.随机选择一个整数e，$1< e < \phi(n)$，且e与$\phi(n)$ 互素（我们知道，此时$e^{\phi(n)} \equiv 1 (mod  n)$）.例如我们在1到2668之间，随机选择了17，e = 17。\par
5.计算e对于$\phi(n)$的模乘法逆元d，当$gcd(e,\phi(n)) =1$，$ed \equiv 1 (mod \ \phi(n)) \Rightarrow d = (1+k\phi(n)) / e,k \in \mathbb{Z}$,代入各值，$d=(1+2668k)/17$,可以依次给k赋值，取d为整数的序偶，得到一系列(k,d),(1,157)、(18,2825)、(35,5493) $\ldots$,随机选一个序偶，比如(1,157)，也就是d=157.\par
6.将n和e封装成公钥，n和d封装成私钥，即公钥为：n = 2773，e = 17，私钥为：n = 2773，d = 157。\par
(2) 用公钥加密字符串\par
假设我们加密一个字符"A"，首先字符要用数值表示（）这就是编码，信源编码），一般用Unicode或ASCII码表示，此处我们用ASCII码表示，
"A"的ASCII码十进制为65(十六进制0x41)，我们用m来代替明文(message)，c来代替密文(cipher)，m = 65，RSA加密公式：$m^e \equiv c (mod n)$,代入各值$65^{17} (mod \ 2773) \equiv 6,599,743,590,836,592,050,933,837,890,625 (mod \ 2773) \equiv 332 (mod \ 2773),c=332$\par
(3) 用私钥解密密文\par
RSA解密公式：$c^d \equiv m (mod \ n)$,代入各值，$c^d \equiv 332^{157} \equiv 6.5868707484014117339891253968203e+395 \equiv 65  (mod \ 2773),m=65$.

\subsection{公私钥对的生成}

RSA的理论很容易看明白，但是当您坐下来准备实现一个RSA算法时，我这里说的实现，不是利用OpenSSL等库来实现，这些库基本的RSA加密过程函数已有实现好了，你只需要了解RSA的过程原理依次调用就可以，而是利用一些基础的数学函数库来实现RSA算法。\par
而在具体做这些底层实现时，会有很多细节问题需要考虑，首先确定好RSA系统的位数后，大素数p和q如何产生？大数如何计算？e如何产生？等等，整个过程是有很多细节需要考虑，而且在密钥产生过程中，如果考虑不够全面，对攻击者来说会有“漏”可捡，而这样的要求你对一个编程者提出来是不公平的，他很难达到这样的要求，道理很简单，他不是数学家，不是密码学家，那么怎么解决？标准。这也就是说你可以看到大量的NIST FIPS和SP标准，以及RFC、ANSI标准在详细描述实现的细节，可以去看看文档"OpenSSL FIPS 140-2 Security Policy"，这里面提到OpenSSL在实现时参考的一些标准。实现细节大家可以去看这些标准，以及其他资料。\par
下面我引用一个帖子里\footnote{\url{https://stackoverflow.com/questions/18264314/generating-a-public-private-key-pair-using-an-initial-key}}的一段原文，对于RSA密钥生成会有一个宏观的了解。
\begin{lstlisting}
	The algorithm for generating an RSA key pair boils down to finding a set of big, prime numbers, that fulfil some algebraical properties and that are of appropriate size. If you need a 2048 bit RSA key, you will typically look for 2 prime number, each having a a rough length of 1024 bits.
	
	The process of finding a prime number is trial-and-error: you randomly pick an integer of appropriate size, and test if it is prime. If it is not, you retry.
	
	In the real world, the random generator that drives the algorithm is a deterministic PRNG which is seeded with a secret of appropriate entropy (e.g. 128 bits of true randomness).
	
	In your case, the PRNG seed can be derived from a user secret or even from another key (provided it is secret of course). Derivation should be performed with a salted KDF like HKDF, PBKDF2, etc.
	
	You don't specify which crypto library you use: whatever it is, you must be clear on how it draw randomness and how to define the seed of the PRNG.
\end{lstlisting}
从上面的讨论中，我们也可以体会到随机数生成在加密体制中是非常重要的功能，他不仅仅在流加密中。